/*Copyright (C) 2013-2023 LZE*/
#include<bits/stdc++.h>
#define fo(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
#define INF 0x7fffffff
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef const long long cll;
const int N = 500010;
const int M = 1000010;
int n, m;
namespace SPFA {
    struct GraphEdge {
        ll to, next, w;
        GraphEdge() {}
    } edge[M];
    int head[N], cnt = 0;
    void add(const int &u, const int &v, const int &w) {
        edge[++cnt].to = v;
        edge[cnt].w = w;
        edge[cnt].next = head[u];
        head[u] = cnt;
    }
    int count[N];
    queue<int> q;
    bool vis[N] = {0};
    ll dis[N];
    bool spfa(const int &s) {
        q.push(s);
        dis[s] = 0; vis[s] = true;
        int p, t;
        while(!q.empty()) {
            p = q.front(); q.pop();
            vis[p] = false;
            for(int i = head[p]; i; i = edge[i].next) {
                t = edge[i].to;
                if(dis[t] > dis[p] + edge[i].w) {
                    dis[t] = dis[p] + edge[i].w;
                    if(!vis[t]) {
                        vis[t] = true;
                        q.push(t);
                        if(++count[t] > n) {
                            return false;
                        }
                    }
                }
            }
        }
        return true;
    }
};
struct GraphNode {
    ll to, w;
    GraphNode() {}
    GraphNode(cll &x, cll &y) : to(x), w(y) {}
    bool operator < (const GraphNode &x) const {
        return w > x.w;
    }
} p;
struct GraphEdge {
    ll to, next, w;
    GraphEdge() {}
} edge[M];
int head[N], cnt = 0;
void add(const int &u, const int &v, const int &w) {
    edge[++cnt].to = v;
    edge[cnt].w = w;
    edge[cnt].next = head[u];
    head[u] = cnt;
}
priority_queue<GraphNode> q;
ll dis[N];
bool vis[N];
ll ans;
int main() {
    scanf("%d%d", &n, &m);
    int x, y, w;
    for(int i = 1; i <= m; i++) {
        scanf("%d%d%d", &x, &y, &w);
        add(x, y, w);
        SPFA::add(x, y, w);
    }
    for(int i = 1; i <= n; i++) SPFA::add(n + 1, i, 0);
    for(int i = 0; i <= n + 1; i++) SPFA::dis[i] = INF;
    if(!SPFA::spfa(n + 1)) {
        printf("-1\n");
        return 0;
    }
    for(int i = 1; i <= n; i++) {
        for(int j = head[i]; j; j = edge[j].next) {
            edge[j].w = edge[j].w + SPFA::dis[i] - SPFA::dis[edge[j].to];
        }
    }
    for(int s = 1; s <= n; s++) {
        for(int i = 0; i <= n + 1; i++) {
            dis[i] = INF;
            vis[i] = 0;
        }
        dis[s] = 0;
        q.push(GraphNode(s, 0));
        while(!q.empty()) {
            p = q.top(); q.pop();
            if(vis[p.to]) continue;
            vis[p.to] = true;
            for(int i = head[p.to]; i; i = edge[i].next) {
                GraphEdge t = edge[i];
                if(dis[t.to] > dis[p.to] + t.w) {
                    dis[t.to] = dis[p.to] + t.w;
                    q.push(GraphNode(t.to, dis[t.to]));
                }
            }
        }
        ans = 0;
        for(int i = 1; i <= n; i++) {
            if(dis[i] == INF) ans += i * 1000000000ll;
            else ans += i * (dis[i] + SPFA::dis[i] - SPFA::dis[s]);
        }
        printf("%lld\n", ans);
    }
    return 0;
}